# 目标：对给出列表使用QuickSort使之升序
def Partition_List(L: list, low: int, high: int) -> int:
    pivot = L[low]  # 取第一项为关键词
    # print(L, "\n    start:", start, "high:", high, "pivot:", pivot)
    while (low < high):
        # print("此时有\n",L, "start:", start, "high:", high, "\n开始本轮操作：")
        # 不断执行两端替换操作直到 start=high 时确定枢轴位置
        while (low < high and L[high] >= pivot):
            high -= 1
            # print("前移high",L, "\n    start:", start, "high:", high)
        if (low < high):
            # start=high 或 L[high]不大于枢轴值
            L[low] = L[high]
            low += 1
            # print("L[high]不够大时替换掉L[start]，后移low\n",L, "\n    start:", start, "high:", high)
            # 此时L[start]替换为L[high]值
        while (low < high and L[low] <= pivot):
            low += 1
            # print("后移low",L, "\n    start:", start, "high:", high)
        if (low < high):
            # start=high 或 L[start]不小于枢轴值
            L[high] = L[low]
            high -= 1
            # print("L[start]不够大时替换掉L[high]，前移low\n",L, "\n    start:", start, "high:", high)
            # 此时L[high]替换为L[start]值
    # print("L:", L, "\n第", start+1, "位为枢轴")
    L[low] = pivot
    # 对L的一次划分完成，返回枢轴位置
    return low


def QSort_List(L: list, start: int, end: int) -> list:
    if (start < end):
        pivot = Partition_List(L, start, end)
        QSort_List(L, start, pivot-1)
        QSort_List(L, pivot+1, end)
    return L


def QuickSort_List(L: list) -> list:
    QSort_List(L, 0, len(L)-1)
    return L


# Partition_List(a, 0, 7)
# QSort_List(a, 0, 7)
# QuickSort_List(a)


a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]


def QuickSort_NoNewList(L: list) -> list:
    mid = len(L) // 2
    pivot = L[mid]
    for i in range(0, len(L)):
        # 使用双指针 前<pivot<后时不交换
        pass
    return L


def QuickSort_NewList(L: list) -> list:
    mid = len(L) // 2
    pivot = L[mid]
    L_copy = list(L)
    for i in range(0, mid):
        # 对 x< pivot 交换位置
        pass
    for i in range(mid, len(L)):
        # 对 y < pivot 交换位置
        pass
    return L
